# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
# include <stdbool.h>

////===================Node��㶨��======================= 
typedef struct Node{
	
	int data;
	struct Node * pNext;
	
}NODE, *PNODE;

 
PNODE create_Link(void);
void traverse_Link(PNODE pHead);
bool is_Empty(PNODE pHead);
int length_Link(PNODE pHead);
void sort_Link(PNODE pHead); 
bool insert_Node(PNODE pHead,int pos,int val);
bool delete_Node(PNODE pHead,int pos);
//===================���������======================= 
void main(){
	
	//����һ��ͷָ�룬���ڻ�ȡ���� 
	PNODE pHead = NULL;
	pHead = create_Link();
	
	//�������� 
	traverse_Link(pHead);
	
	//�ж������Ƿ�Ϊ��
//	is_Empty(pHead); 
	
	//ͳ����������
//	length_Link(pHead); 
	
	//��������������
	// sort_Link(pHead); 
	insert_Node(pHead,3,666);

	delete_Node(pHead,4);
	traverse_Link(pHead);
	

	return ;
}

//===================��������======================= 

//�������� 
PNODE create_Link(){
	
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	pHead->pNext = NULL;
	
	PNODE pTail = pHead;
	if(NULL == pHead){
		
		printf("��̬����ʧ�ܣ������˳���");
		exit(-1);
		
	}
	
	
	int num;int i;
	int data;
	
	printf("������Ҫ�����Ľ������");
	scanf("%d", &num);
	
	for(i = 0; i<num; i++){
		
		printf("�������%d���������ݣ�",i+1);
		scanf("%d",&data);
		
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if(NULL == pNew){
			
			printf("��̬����ʧ�ܣ������˳���");
			exit(-1);

		}
		pNew->data = data;
		pNew->pNext = NULL;
		
		pTail->pNext = pNew;
		pTail = pNew;
		pNew = NULL;
		
	}
	
	
	
	return pHead;
}

//�������� 
void traverse_Link(PNODE pHead){
	
	PNODE p = NULL;
	p = pHead->pNext;
	
	while(p != NULL){
		
		printf("%d\n",p->data);
		p = p->pNext;
	
	}

	return;
}

//�ж������Ƿ�Ϊ��
bool is_Empty(PNODE pHead){

	if(NULL == pHead->pNext){
		
		printf("it is empty!");
		return true;
		
	}
		
	printf("it is not unempty!");
	return false;
		
	

	

} 

//ͳ�������ĳ���
int length_Link(PNODE pHead){
	
	PNODE p = NULL;
	p = pHead->pNext;
	int i;i=0;
	
	while(NULL != p){
		
		i++;
		p = p->pNext;
		
	}
	
	printf("\n��������������Ϊ:%d\n",i);
	return i;
}

//��������������
void sort_Link(PNODE pHead){
	
	int i,j,temp;
	int len = length_Link(pHead);
	
	PNODE pStart = NULL;
	PNODE p = NULL;

	
	for(i=0, pStart = pHead->pNext; i<len-1; i++, pStart=pStart->pNext){
		for(j=i+1,p = pStart->pNext; j<len; j++, p=p->pNext){
			
			if(pStart->data > p->data){
				
				temp = pStart->data;
				pStart->data = p->data;
				p->data = temp;
				
			}
			
		}
	}
	
	return ;
}

//插入节点
bool insert_Node(PNODE pHead,int pos,int val){

	int i = 0;
	PNODE p = pHead;

	while(p != NULL && i < pos - 1){

		p = p->pNext;
		i++;
	}

	printf("i: %d\n",i);

	if(i > pos - 1 || NULL == p){

		return false;

	}

	PNODE pNew = (PNODE)malloc(sizeof(NODE));

	if(pNew == NULL){

		printf("eroor" );
		return false;

	}

	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext = pNew;	
	pNew->pNext = q;
	
	return true;
}

bool delete_Node(PNODE pHead,int pos){

	int i = 0;
	PNODE p = pHead;

	while(p != NULL && i < pos - 1){

		p = p->pNext;
		i++;
	}

	if(i > pos - 1 || NULL == p){

		return false;

	}

	PNODE pDel = p->pNext;
	p->pNext = pDel->pNext;
	free(pDel);
	pDel = NULL;
	
	return true;
}


